Optical fiber transmission systems have made possible high speed digital networks having data rates in excess of 1000 million bits per second (1000 Mbps). Many different kinds of communication systems based on fiber optic transmission have been implemented or proposed. One proposed system operates by sending messages called "packets" between users. Each packet includes a destination address which is used to route the packet through the various switches in a telephone system. This type of system is referred to as a packet switching network.
A modern optical fiber can easily transport signals at the rate of several gigabits per second, while the bit rates of present switches (even experimental switches) are lower by two orders of magnitude. In order to fully utilize the high data rates of modern optical fiber communications systems, it is necessary to significantly increase switching speeds.
The switches operate between input and output ports connected to the optical fibers. There may be hundreds of optical fibers connected to a single switch. To properly route a packet arriving on one of the input ports, the switch must read the address portion of the packet and then transfer the packet to the desired output port. The switching must be accomplished for each packet arriving on each optical fiber.
In general, the switch is constructed from a plurality of switching elements organized into stages. Each switching element has a set of inputs and a set of outputs. The inputs in the first stage are connected to the input optical fibers, and the outputs of the switching elements in the last stage are connected to the output optical fibers. The remaining switching elements are connected such that the inputs to a switching element in a given stage are connected to outputs of switching elements in the previous stage. Each packet is routed through the switch by setting the connections between the inputs and the outputs of the relevant switching elements.
Cross-connect switches may be divided into two broad classes. The first class includes cross-connect switches in which a single controller determines the routing of the packet through the cross-connect switch. This type of cross-connect switch has not been found to be practical for high-speed packet switching systems, since the controller must operate at unrealistically high speeds. The second type of cross-connect switch that has been proposed for packet-switching networks is a self-routing switch. In this type of switch, the switching elements in each stage examine a portion of the packet address and use this information for setting the connections between the input and output lines of the switching element.
One class of self-routing cross-connect switch is referred to as a Banyan network. Each of the switching elements consists of a 2.times.2 switching element having two inputs and two outputs. The switching element examines a predetermined bit of the packet address for each of the two packets received on its inputs. The bit in question is determined by the stage in which the switching element is located. The switching element then sets its internal connections according to the two address bits in question.
Banyan networks may suffer from two types of "blocking". A network is said to be blocking if two packets must be routed over the same connection between two switching elements. This will occur when the two packets input to a given switching element must be switched such that both packets leave the switching element on the same output thereof. This situation occurs if both packets have the same destination address. This situation is referred to as "output blocking". Output blocking cannot be avoided, since the two packets in question are destined for the same output of the cross-connect switch.
Output blocking can lead to the loss of the information being blocked. This result can be avoided if the cross-connect switch can detect two packets having the same destination address and buffer one of these in an input queue. A "reservation scheme" is used to choose which of the packets to send and guarantee that all destination addresses are distinct.
The second type of blocking is referred to as "internal blocking". This occurs when two packets with distinct destination addressed must traverse the same internal link in the cross-connect switch. In other words, the two packets have overlapping paths in the cross-connect switch. To overcome internal blocking within the Banyan network, a preprocessor is used to process the incoming packets. One form of preprocessing sorts the packets so that they start at different inputs from those that would cause blocking. In this way, the packets will follow different paths and, if sorted properly, can avoid internal blocking.
The most common sorting scheme suggested is the Batcher network. This sorting scheme suffers from several deficiencies. First, the Batcher network is more complex than the Banyan network which it controls. The number of switching elements in the Batcher network is greater than the number of element in the Banyan network. Second, the Batcher network must make comparisons between the destination addresses to perform the sort. A precise packet bit alignment must be maintained throughout the sorting network. This alignment requirement imposes constraints on the speed with which the Batcher network operates; hence it is difficult to construct a system that operates at a speed sufficient to fully realize the potential of the optical fiber system. The experimental implementation of the Batcher-Banyan network, for example, only achieves the rate of 139 Mbps for a 32.times.32 switch.
Broadly, it is an object of the present invention to provide an improved packet routing network switch.
It is a further object of the present invention to provide a switch having a nonblocking characteristic while operating at speeds commensurate with data rates of optical fiber networks.
These and other objects of the present invention will become apparent to those skilled in the art from the following detailed description of the invention and the accompanying drawings.